Search graphs, or lattices, in automatic speech recognition (ASR) systems can be used to map an input utterance to one or more output text strings. Some implementations attempt to select text string(s) that have a minimal probability of having one or more word errors. It may be more accurate to instead select text strings that have the smallest expected word error rate (e.g., the smallest edit distance) to a correct transcription of the utterance. However, doing so can be computationally expensive.